package algorithm.array;

import java.util.Arrays;

public class test {
    public static void main(String[] args) {
//        String[] strings = {"1","2","3"};
        int[] nums = {2,3,1,2,4,3};
        int i = minSubArrayLen(7, nums);
        System.out.println(i);

        Arrays.sort(nums);
        System.out.println(Arrays.toString(nums));



    }






public int[][] generateMatrix(int n) {
    int[][] arr = new int[n][n];
    //按照从左到右 从上到下 从右到左 从下到上 填入顺序循环，从 arr[0][0]到 arr[n-1][n-1]
    //定义当前左右上下边界 left,right,top,bottom （每层填充后需要更新），各边界填完后，边界向内缩 1。
    // 初始值 num = 1，迭代终止值 tar = n * n；
    int num = 1, left = 0, right =n-1, top =0, bottom = n-1;
    while (num <= n*n){
        //从左到右（可以到 right，因为 top++ 之后就是下一层的right了）
        for (int i = left; i <= right; i++) {
            arr[top][i] = num++;
        }
        top++;
        // 从上到下
        for (int i = top; i <= bottom; i++) {
            arr[i][right] = num++;
        }
        right--;
        // 从右到左
        for (int i = right; i >= left; i--) {
            arr[bottom][i] = num++;

        }
        bottom--;
        // 从下到上 (top已经减过了，在下一层了，可以到top)
        for (int i = bottom; i >= top; i--) {
            arr[i][left] = num++;
        }
        left++;
    }
    return arr;
}




//    滑动窗口, 使用 `left` 和 `right` 变量初始化窗口的两端。初始状态下，start、end都指向下标 0，sum为两指针的“共同财产”
//每一轮迭代，将 nums[end]加到 sum, 如果 sum≥target，则更新子数组的最小长度（end−start+1），
// 然后将  sum - nums[start] 并将 start指针右移，直到 sum<target，在此过程中同样更新子数组的最小长度。在每一轮迭代的最后，将 end右移。
public static int minSubArrayLen(int target, int[] nums) {
    int left = 0, right = 0;
    int minLen = Integer.MAX_VALUE;
    int sum = 0;

    while (right < nums.length){
        sum +=nums[right];//每次自动扩大窗口

        while (sum >=target ){
            minLen = Math.min((right -left+1),minLen);
            sum -= nums[left];
            ++ left;
        }
        ++ right ;
    }
    return (minLen == Integer.MAX_VALUE) ? 0 : minLen;
}

//    双指针思路，从最左最右两边开始判断，直到最中间，选择较大的元素放在新数组的n-1位置，就是逆序放置。
//    使用两个指针分别指向位置 0 和 n−1，每次比较两个指针对应的数，选择较大的那个逆序放入答案并移动指针。
public int[] sortedSquares(int[] nums) {
    int len = nums.length;
    int[] arr = new int[len];//新数组

    for (int left = 0, right = len-1, pos = len; left <= right;) {
        --pos;
        if (nums[left] * nums[left] > nums[right] * nums[right]){
            arr[pos] = nums[left] * nums[left];
            ++left;
        }else {
            arr[pos] = nums[right] * nums[right];
            --right;
        }

    }
    return arr;
}





public int removeElement(int[] nums, int val) {
    //数组的元素在内存地址中是连续的，不能单独删除数组中的某个元素，只能覆盖。
    int left = 0, right = 0;
    while (right < nums.length) {
        //等于val，需要被覆盖
        //不等于val，OK的，都移动
        if(nums[right] == val){
            right++;
        }else {
            nums[left] = nums[right];
            left++;
            right++;
        }
    }
    return left ;
}


public int binarySearch(int[] nums, int target) {
    int left = 0, right = nums.length-1;

    while (left<=right){

        int mid = (left+right)/2;
        if (nums[mid] == target){
            return mid;
        }else if (nums[mid] < target){
            left = mid+1;

        }else {
            right = mid-1;
        }

    }
    return -1;
}
}
